#!/usr/bin/env python3
import time
import unittest

import z3
import bisect

"""
找到一组6个字母的组合让其hash=593779930,这里java代码的int会超范围，而python支持任意大数，需要注意
// lowercase
private static boolean hash(final String s) {
    int n = 7;
    final int n2 = 593779930;
    for(int i = 0; i < 6; ++i) {
        n = n * 31 + s.charAt(i);
    }
    return n == n2;
}
"""


class TestWeekHash(unittest.TestCase):
    def int32(self, x):
        """
        python 整数是任意大小的，这里模拟java版本的int32
        :param x:
        :return:
        """
        return x & 0xFFFFFFFF  # 保留低32位

    def week_hash(self, s):
        # 弱哈希算法
        n = 7
        for letter in list(s):
            n = self.int32(n * 31) + ord(letter)
        return n

    def test_week_hash(self):
        s = input('input a string\n')
        print(f'{s} hash : {self.week_hash(s)}')

    def binary_search(self, arr, target):
        # 二分查找
        i = bisect.bisect_left(arr, target)
        if i != len(arr) and arr[i] == target:
            return i
        return -1

    def test_solve_week_hash_recursion(self):
        """
        暴力递归查找符合条件的字符组合
        """
        chars = list('abcdefghijklmnopqrstuvwxyz')
        password_len = 6

        def force_brute(pwd_arr, position):
            if position >= password_len:
                if self.week_hash(''.join(pwd_arr)) == 593779930:
                    print(f'{pwd_arr}')
                return
            # 循环候选字母列表
            for i in range(len(chars)):
                # 对于position位置的字母，循环放置候选字母
                pwd_arr[position] = chars[i]
                # 对于下一个字母做同样操作
                force_brute(pwd_arr, position + 1)

        force_brute(['a'] * password_len, 0)

    def test_solve_week_hash_loop(self):
        """
        暴力查找符合条件的字符组合
        :return:
        """
        chars = list('abcdefghijklmnopqrstuvwxyz')
        password_len = 6
        pwd_arr = ['a'] * password_len
        while True:
            # 这里可以添加密码验证逻辑
            if self.week_hash(''.join(pwd_arr)) == 593779930:
                print(f'{pwd_arr}')
                break
            # pos设置为最后一个字母
            pos = password_len - 1
            while pos >= 0:
                # 当pos位置的字母不是最后一个字母时
                if pwd_arr[pos] != chars[len(chars) - 1]:
                    # 把pos位置的字母设置为候选字母表的下一个
                    pwd_arr[pos] = chars[self.binary_search(chars, pwd_arr[pos]) + 1]
                    break
                else:
                    # 否则pos位置的字母设置为第一个候选字母
                    pwd_arr[pos] = chars[0]
                    pos = pos - 1
            # 检查是否完成所有组合
            if pos < 0:
                break

    def test_solve_week_hash(self):
        """
        耗时31毫秒，java的loop暴力算法耗时671毫秒
        :return:
        """
        start = time.perf_counter()
        n = 7
        letters = [z3.Int(f's_{i}') for i in range(6)]
        # 计算hash(z3的int也是无限大小的)计算出z3大int表示的hash(n)
        for i in letters:
            n = n * 31 + i

        solver = z3.Solver()

        for i in letters:
            solver.add(z3.And(i >= ord('a'), i <= ord('z')))
        # n转换为java算出的有限位数的hash
        solver.add((n % 2 ** 32) == 593779930)

        if solver.check() == z3.sat:
            m = solver.model()
            s = ''
            for i in letters:
                s += (f'{chr(m.evaluate(i).as_long())}')
            print(s)
        end = time.perf_counter()
        print(f"耗时: {(end - start) * 1000:.2f}毫秒")

